Consulta de Guías Docentes



Academic Year/course: 2021/22

30214 - Computer Science Theory


Syllabus Information

Academic Year:
2021/22
Subject:
30214 - Computer Science Theory
Faculty / School:
110 - Escuela de Ingeniería y Arquitectura
326 - Escuela Universitaria Politécnica de Teruel
Degree:
439 - Bachelor's Degree in Informatics Engineering
443 - Bachelor's Degree in Informatics Engineering
ECTS:
6.0
Year:
2
Semester:
First semester
Subject Type:
Basic Education
Module:
---

1. General information

1.1. Aims of the course

The course and its expected results respond to the following approaches and objectives:

  • Train the student so that he/she can abstract problems to solve using a computer.
  • Know the basic computation models on which current computers are based and identify the most adapted to each problem.
  • Assimilate paradigms of well-studied problems in the context of computing so that you can reduce or adapt them to the problems that arise.
  • Know the capabilities and limitations of automatic problem solving and evaluate the necessary resources for it.

These approaches and objectives are aligned with some of the Sustainable Development Goals, SDGs, of the 2030 Agenda (https://www.un.org/sustainabledevelopment/en/) and certain specific goals, in such a way that the acquisition of the Learning outcomes of the subject provide training and competence to the student to contribute to a certain extent to their achievement:

Goal 1: End poverty in all its forms everywhere.
Target 1.4: By 2030, ensure that all men and women, in particular the poor and the vulnerable, have equal rights to
economic resources, as well as access to basic services, ownership and control over land and other forms of
property, inheritance, natural resources, appropriate new technology and financial services, including microfinance.


Goal 8: Promote inclusive and sustainable economic growth, employment and decent work for all.
Target 8.2: Achieve higher levels of economic productivity through diversification, technological upgrading and
innovation, including through a focus on high-value added and labour-intensive sectors.


Goal 16: Promote just, peaceful and inclusive societies.
Target 16.5: Substantially reduce corruption and bribery in all their forms.

1.2. Context and importance of this course in the degree

The Theory of Computation is a basic course taught in the second year of the degree. This particular temporal location allows students to apply the knowledge acquired in this subject to all courses of the degree: decidability, language theory and complexity. These tools will be part of the set of fundamental skills and methods that the computer science engineer will apply in his work.

1.3. Recommendations to take this course

It is convenient that the student has taken the courses of Programming I (1st Semester) and Discrete Mathematics (2nd Semester).

2. Learning goals

2.1. Competences

After passing the course, the student will be more competent to ...

  • Solve problems and make decisions with initiative, creativity, and critical thinking.
  • Communicate and transmit knowledge, abilities and skills in Spanish.
  • Use the techniques, skills and tools of Engineering necessary for the practice of it.
  • Learn continuously and develop autonomous learning strategies.
  • Apply information and communication technologies in Engineering.
  • Understand and master the basic concepts of discrete mathematics, logic, algorithms and computational complexity, and their application to solve engineering problems.
  • Use computers, operating systems, databases and computer programs with applications in engineering.

2.2. Learning goals

The student, to pass this subject, must demonstrate the following results ...

  • Know the basic computation models.
  • Find the simplest calculation model for each problem.
  • Discard wrong solutions as too simple for given problems.
  • Adequately describe the computation processes.
  • Apply the formalisms of language theory in problem solving.
  • Transform informal statements into formal statements and vice versa.
  • Know the limitations of automatic problem solving.
  • Identify basic unsolvable problems such as the halting problem or the virus detection problem.
  • Analyze the cost in time and memory of an algorithm.
  • Identify problems that require too many computational resources.

2.3. Importance of learning goals

The set of learning outcomes can be summarized by saying that the student will be able to abstract a problem to be solved using a computer, identifying the most appropriate computation model, reducing it to known problems and identifying the limitations of its resolution and the resources necessary for it. Having learned to do it well and efficiently is of vital importance in the context of Computer Science studies of which one of its pillars is solving computation problems.

3. Assessment (1st and 2nd call)

3.1. Assessment tasks (description of tasks, marking system and assessment criteria)

The student must demonstrate that he has achieved the expected learning outcomes through the following assessment activities

At the Zaragoza School of Engineering and Architecture:

Laboratory practical work (30%). On the one hand, a previous report will be assessed where the student must have identified the information needs to solve the problems raised and their use in the resolution. The critical capacity when selecting alternatives and the degree of justification of the solution reached will also be assessed.

On the other hand, the fluency in the use of the computer to solve problems will be assessed. The solutions implemented for each of the exercises proposed for the practical sessions will also be evaluated, taking into account the quality of the procedures and efficient resolution strategies in the computer.

Written exam (70%) in which questions and/or problems in the field of Computer Science will be proposed to be solved by means of a computer, with a typology and level of complexity similar to that used during the course. The quality and clarity of the resolution strategy, as well as its efficiency, will be assessed.

A minimum mark of 4 points out of a total of 10 is required in the written exam to pass the course. If this minimum grade is obtained, then the written exam weighs 70% in the grade of the course and, if this minimum is not reached, then the grade in the course is that of the written exam.

At the Polytechnic University School of Teruel:

The final grade for the call in the ordinary call is divided as follows:

Written exam. 70% of the final grade. It will consist of a part of theory and another of problems. In the middle of the course there will be a partial test that will allow to "advance" grade for the exam.

Theoretical work. 5% of the final grade. It will consist of a thematic work to be defined during the course that will deal with some of the subjects of the course.

Practical work. 25% of the final grade. There will be several deliverable practical works throughout the course.

A minimum of 4 points out of a total of 10 is required in the written exam to pass the course. If this minimum grade is obtained, then the weighting indicated above will be carried out. If this minimum is not reached, then the grade in the course is that of the written exam.

In the case of the extraordinary call (September), the final grade will be the grade of the extraordinary exam, taking into account that this exam will have a part of theory and problems that will be 75% of the final grade, and a part of practical works that it will be 25% of the final grade. The marks of the partial exam and of the theoretical work will not be kept for the September call.

Organization of evaluation activities

The student will pass the course by carrying out the activities listed in the previous section and with the relative weightings indicated there. The global assessment will be divided into two parts corresponding to the cited activities and the date of its completion will be specified in advance by the center. Students who have passed activity 1) during the course will also be able to present themselves to improve their grade on the dates of the global assessment.

4. Methodology, learning tasks, syllabus and resources

4.1. Methodological overview

The learning process that is designed for this course is based on:

  • The presentation of the contents of the subject in lectures in the classroom
  • Solving problems in class.
  • Personal study of the subject by students.
  • The development of lab assignments by students, guided by teachers in the laboratory
  • Solving simple problems of increasing difficulty proposed by the teachers.

Keep in mind that the subject has both theoretical and practical orientation. Therefore, the learning process emphasizes both student attendance at lectures, as in the practical work in the laboratory, in solving simple problems of increasing difficulty, and individualized study.

4.2. Learning tasks

The course includes the following learning tasks: 

  • In classes taught in the classroom, the program of the course will be presented.
  • In classes of case studies, problems will be solved using the concepts and techniques presented in the course syllabus.
  • Practical work sessions will be held in a computer lab.

4.3. Syllabus

The course will address the following topics. The course topics are organized around three pillars:

(1) Theory of formal languages, with an emphasis on regular languages and context-free languages;

(2) Fundamentals of Computability, to narrow what problems can be solved algorithmically;

(3) Fundamentals of Algorithmic Complexity, to define what is the efficiency of an algorithmic solution and the number of resources an algorithm needs.

  • Topic 0: Preliminaries
    Mathematical Preliminaries: sets, functions, relations, induction.
    Definition of alphabet and language.

  • Topic 1: Regular Languages
    Regular expressions and regular languages.
    Deterministic finite automata (DFA) and nondeterministic finite automata (nDFA)
    Equivalence between DFA and nDFA.
    Properties of regular languages. Pumping Lemma.

  • Topic 2: Context-Free Languages
    Grammars and context-free languages.
    Pushdown automata.
    Simplification of grammars.
    Properties of context-free languages. Pumping Lemma.

  • Topic 3: Computability
    Turing machines.
    Languages and Turing machines. Church-Turing thesis.
    Decidability. Non-decidable problems.

  • Topic 4: Complexity
    The classes of languages P and EXP.
    The classes of languages NP and NP-complete.

The concepts, methods and tools of the above paragraphs are illustrated through examples, as realistic as possible, within the areas of computer security, cryptography, natural language processing and compression of information.

4.4. Course planning and calendar

Scheduling of sessions and presentation of works

The schedule of the course will be defined by the School in the academic calendar of the corresponding academic year.

Student Work

The dedication of the student to achieve the learning outcomes in this course is estimated at 150 hours distributed as follows:

In the School of Engineering and Architecture of Zaragoza:

  •     56 hours, approximately, of classroom activities (lectures, problems and laboratory)
  •     40 hours of teamwork
  •     51 hours of personal study (study booktexts and lecture notes, problem solving, preparing lessons and lab assignments)
  •     3 hours deoted to the written final exam


At the Polytechnic University School of Teruel:

    60 hours of classroom activities (lectures, problems and laboratory)
    30 hours of teamwork
    55 hours of personal study (study booktexts and lecture notes, problem solving, preparing lessons and lab assignments)
    5 hours of evaluation activities

 

4.5. Bibliography and recommended resources

Teruel:

http://psfunizar10.unizar.es/br13/egAsignaturas.php?codigo=30214&Identificador=12956

Zaragoza:

http://psfunizar10.unizar.es/br13/egAsignaturas.php?codigo=30214&Identificador=13381


Curso Académico: 2021/22

30214 - Teoría de la computación


Información del Plan Docente

Año académico:
2021/22
Asignatura:
30214 - Teoría de la computación
Centro académico:
110 - Escuela de Ingeniería y Arquitectura
326 - Escuela Universitaria Politécnica de Teruel
Titulación:
439 - Graduado en Ingeniería Informática
443 - Graduado en Ingeniería Informática
Créditos:
6.0
Curso:
2
Periodo de impartición:
Primer semestre
Clase de asignatura:
Formación básica
Materia:
Materia básica de grado

1. Información Básica

1.1. Objetivos de la asignatura

La asignatura y sus resultados previstos responden a los siguientes planteamientos y objetivos:

Los objetivos de la asignatura son fundamentalmente de cuatro tipos:

  1. Capacitar al estudiante para que pueda abstraer problemas a resolver mediante un computador.
  2. Conocer los modelos de cálculo básicos en los que se basan los computadores actuales e identificar el más adaptado a cada problema.
  3. Asimilar paradigmas de problemas bien estudiados en el contexto de la informática para que pueda reducirlos o adaptarlos a los problemas que se le planteen.
  4. Conocer las capacidades y limitaciones de la resolución automática de problemas y evaluar los recursos necesarios para ello.

Estos planteamientos y objetivos están alineados con algunos de los Objetivos de Desarrollo Sostenible, ODS, de la Agenda 2030 (https://www.un.org/sustainabledevelopment/es/) y determinadas metas concretas, de tal manera que la adquisición de los resultados de aprendizaje de la asignatura proporciona capacitación y competencia al estudiante para contribuir en cierta medida a su logro:


Objetivo 1: Poner fin a la pobreza en todas sus formas en todo el mundo.
Meta 1.4: Para 2030, garantizar que todos los hombres y mujeres, en particular los pobres y los vulnerables,
tengan los mismos derechos a los recursos económicos, así como acceso a los servicios básicos, la propiedad y el
control de las tierras y otros bienes, la herencia, los recursos naturales, las nuevas tecnologías apropiadas y los
servicios financieros, incluida la micro-financiación.


Objetivo 8: Promover el crecimiento económico sostenido, inclusivo y sostenible, el empleo pleno y productivo y el trabajo decente para todo.
Meta 8.2: Lograr niveles más elevados de productividad económica mediante la diversificación, la modernización
tecnológica y la innovación, entre otras cosas centrándose en los sectores con gran valor añadido y un uso
intensivo de la mano de obra.


Objetivo 16: Promover sociedades, justas, pacíficas e inclusivas.
Meta 16.5: Reducir considerablemente la corrupción y el soborno en todas sus formas.

1.2. Contexto y sentido de la asignatura en la titulación

La Teoría de la Computación es una asignatura de Formación Básica impartida en el segundo curso de la titulación. Esta particular ubicación temporal permite que los estudiantes puedan aplicar en todas las asignaturas de la titulación los conocimientos adquiridos en esta asignatura: decidibilidad, teoría de lenguajes y complejidad. Estas herramientas formarán parte del conjunto de habilidades y métodos fundamentales que el ingeniero informático aplicará en su trabajo.

1.3. Recomendaciones para cursar la asignatura

Es conveniente que el alumno haya cursado las asignaturas de Programación I (1er Cuatrimestre) y Matemática Discreta (2º Cuatrimestre).

2. Competencias y resultados de aprendizaje

2.1. Competencias

Al superar la asignatura, el estudiante será más competente para...

Resolver problemas y tomar decisiones con iniciativa, creatividad y razonamiento crítico.

Comunicar y transmitir conocimientos, habilidades y destrezas en castellano.

Usar las técnicas, habilidades y herramientas de la Ingeniería necesarias para la práctica de la misma.

Aprender de forma continuada y desarrollar estrategias de aprendizaje autónomo.

Aplicar las tecnologías de la información y las comunicaciones en la Ingeniería.

Comprender y dominar los conceptos básicos de matemática discreta, lógica, algoritmia y complejidad computacional, y su aplicación para la resolución de problemas propios de la ingeniería.

Usar ordenadores, sistemas operativos, bases de datos y programas informáticos con aplicación en ingeniería.

2.2. Resultados de aprendizaje

El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados...

Conoce los modelos de cálculo básicos.

Encuentra el modelo de cálculo más simple para cada problema.

Descarta soluciones incorrectas por ser demasiado simples para problemas dados.

Describe adecuadamente los procesos de cálculo.

Aplica los formalismos de la teoría de lenguajes en la resolución de problemas.

Transforma enunciados informales en enunciados formales y viceversa.

Conoce las limitaciones de la resolución automática de problemas.

Identifica problemas irresolubles básicos como el problema de parada o el de detección de virus.

Analiza el coste en tiempo y memoria de un algoritmo.

Identifica problemas que requieren demasiados recursos de cálculo.

2.3. Importancia de los resultados de aprendizaje

El conjunto de los resultados de aprendizaje se puede resumir diciendo que el alumno será capaz de abstraer un problema a resolver mediante un computador identificando el modelo de cálculo más adecuado, reduciéndolo a problemas conocidos e identificando las limitaciones de dicha resolución y los recursos necesarios para ella. Haber aprendido a hacerlo bien y con eficiencia es de vital importancia en el contexto de unos estudios de Ingeniería Informática de los que uno de sus pilares es la resolución de problemas.

3. Evaluación

3.1. Tipo de pruebas y su valor sobre la nota final y criterios de evaluación para cada prueba

El estudiante deberá demostrar que ha alcanzado los resultados de aprendizaje previstos mediante las siguientes actividades de evaluacion

En la Escuela de Ingeniería y Arquitectura de Zaragoza:

Trabajo de laboratorio (30%). Por una parte, se evaluará el guión previo donde el estudiante deberá haber identificado las necesidades de información para resolver los problemas planteados y su utilización en la resolución. También se valorará la capacidad crítica a la hora de seleccionar alternativas y el grado de justificación de la solución alcanzada.
Se evaluará, por otra parte, la soltura en el manejo del computador para resolver problemas. También se evaluarán las soluciones implementadas para cada uno de los ejercicios planteados para las sesiones de prácticas, atendiendo a la calidad de los procedimientos y estrategias de resolución eficiente en el computador.

Prueba escrita (70%) en la que se plantearán cuestiones y/o problemas del ámbito de la Ingeniería Informática a resolver mediante un computador, de tipología y nivel de complejidad similar al utilizado durante el curso. Se valorará la calidad y claridad de la estrategia de resolución, así como su eficiencia.

Se requiere una nota mínima de 4 puntos sobre un total de 10 en la prueba escrita para aprobar la asignatura. Si se obtiene esta nota mínima, entonces la prueba escrita pondera un 70% en la nota de la asignatura y, si no se alcanza este mínimo, entonces la calificación en la asignatura es la de la prueba escrita.

En la Escuela Universitaria Politécnica de Teruel:

La nota final de la asignatura en la convocatoria ordinaria se divide de la siguiente forma:

Examen escrito. 70% de la nota final. Constará de una parte de teoría y otra de problemas. A mitad de asignatura habrá una prueba parcial que permitirá "adelantar" nota de cara al examen.

Trabajo teórico. 5% de la nota final. Consistirá en un trabajo de temática a definir durante el curso que tratará sobre alguno de los temas de la asignatura.

Prácticas. 25% de la nota final. Habrá varias prácticas entregables a lo largo del curso.

Se requiere una nota mínima de 4 puntos sobre un total de 10 en la prueba escrita para aprobar la asignatura. Si se obtiene esta nota mínima, entonces se realizará la ponderación antes indicada. Si no se alcanza este mínimo, entonces la calificación en la asignatura es la de la prueba escrita.

En cuanto a la convocatoria extraordinaria (septiembre), la nota final será la nota del examen extraordinario, teniendo en cuenta que ese examen tendrá una parte de teoría y problemas que valdrá el 75% de la nota total y una de prácticas que valdrá el 25%. No se mantendrán para septiembre las notas del parcial ni del trabajo.

Organización de las actividades de evaluación

El alumno superará la asignatura mediante la realización de las actividades enumeradas en el apartado anterior y con las ponderaciones relativas allí señaladas. La evaluación global se desglosará en dos partes correspondientes a dichas actividades y su fecha de realización se especificará con suficiente antelación por el centro. Los alumnos que hubieran superado la actividad 1) durante el curso también podrán presentarse a subir nota en las fechas de la evaluación global.

4. Metodología, actividades de aprendizaje, programa y recursos

4.1. Presentación metodológica general

El proceso de aprendizaje que se ha diseñado para esta asignatura se basa en lo siguiente:

  1. La presentación de los contenidos de la asignatura en clases magistrales por parte de los profesores.
  2. La resolución de problemas planteados en clase.
  3. El estudio personal de la asignatura por parte de los alumnos.
  4. El desarrollo de prácticas por parte de los alumnos, guiadas por los profesores, que desarrollan los conocimientos teóricos.
  5. La resolución de problemas sencillos de dificultad creciente propuestos por los profesores.

 

Se debe tener en cuenta que la asignatura tiene una orientación tanto teórica como práctica. Por ello, el proceso de aprendizaje pone énfasis tanto en la asistencia del alumno a las clases magistrales como en la realización de prácticas en laboratorio, en la resolución de problemas sencillos de dificultad creciente, y en el estudio individualizado.

4.2. Actividades de aprendizaje

El programa que se ofrece al estudiante para ayudarle a lograr los resultados previstos comprende las siguientes actividades...

En las clases impartidas en el aula se desarrollará el programa de la asignatura.

En las clases de problemas se resolverán problemas de aplicación de los conceptos y técnicas presentadas en el programa de la asignatura.

Las sesiones de prácticas de desarrollan en un laboratorio informático. 

4.3. Programa

El programa de esta asignatura se organiza alrededor de tres pilares básicos: (1) Teoría de lenguajes formales, con énfasis en los lenguajes regulares y los independientes de contexto; (2) Fundamentos de Computabilidad, para acotar qué problemas pueden ser resueltos algorítmicamente; (3) Fundamentos de Complejidad Algorítmica, para definir qué es eficiencia de una solución algorítmica y los recursos que necesita un algoritmo.

 

Tema 0: Preliminares

Preliminares matemáticos: conjuntos, funciones, relaciones, inducción.

Definición de alfabeto y lenguaje.

 

Tema 1: Lenguajes Regulares

Expresiones regulares y lenguajes regulares.

Autómatas finitos deterministas (AFD) y no deterministas (AFnD).

Equivalencia entre AFD y AFnD.

Propiedades de los lenguajes regulares. Lema de bombeo.

 

Tema 2: Lenguajes Independientes de Contexto

Gramáticas y lenguajes independientes del contexto.

Autómatas de pila.

Simplificación de gramáticas.

Propiedades de los lenguajes independientes del contexto. Lema de bombeo

 

Tema 3: Computabilidad

Máquinas de Turing.

Lenguajes y Máquinas de Turing. Tesis de Church-Turing.

Decidibilidad. Problemas no decidibles.

 

Tema 4: Complejidad

Clases de lenguajes P y EXP.

Clases de lenguajes NP y NP-completo.

 

Los conceptos, métodos y herramientas de los apartados anteriores se ilustrarán a través de ejemplos, lo más realistas posibles, dentro de los ámbitos de: seguridad informática, criptografía, procesamiento de lenguaje natural y compresión de la información.

4.4. Planificación de las actividades de aprendizaje y calendario de fechas clave

Calendario de sesiones presenciales y presentación de trabajos

El calendario de la asignatura estará definido por el centro en el calendario académico del curso correspondiente.

 

Trabajo del estudiante

La dedicación del estudiante para alcanzar los resultados de aprendizaje en esta asignatura se estima en 150 horas distribuidas del siguiente modo:

 

En la Escuela de Ingeniería y Arquitectura de Zaragoza:

  • 56 horas, aproximadamente, de actividades presenciales (clases teóricas, de problemas y prácticas en laboratorio)
  • 40 horas de trabajo en equipo
  • 51 horas de estudio personal efectivo (estudio de apuntes y textos, resolución de problemas, preparación clases y prácticas)
  • 3 horas de examen final escrito

En la Escuela Universitaria Politécnica de Teruel:

  • 60 horas de actividades presenciales (clases teóricas, de problemas y prácticas en laboratorio)
  • 30 horas de trabajo en equipo
  • 55 horas de estudio personal efectivo (estudio de apuntes y textos, resolución de problemas, preparación clases y prácticas)
  • 5 horas de actividades de evaluación

El calendario de exámenes y las fechas de entrega de trabajos de evaluación se anunciarán con suficiente antelación.

En la Escuela de Ingeniería y Arquitectura del Campus Rio Ebro:
En la Escuela Universitaria Politécnica del Campus de Teruel

4.5. Bibliografía y recursos recomendados

Teruel:

http://psfunizar10.unizar.es/br13/egAsignaturas.php?codigo=30214&Identificador=12956

Zaragoza:

http://psfunizar10.unizar.es/br13/egAsignaturas.php?codigo=30214&Identificador=13381